#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

#include "avl.hpp"
#include "bst.hpp"
#include "map.hpp"
#include "rbt.hpp"

// --------------------------- 随机插入 / 随机删除 ---------------------------
template <typename M>
void testRandomMapCorrectness(const std::string& name, int N) {
  M map;
  std::vector<int> keys(N);
  std::vector<int> values(N);

  for (int i = 0; i < N; ++i) {
    keys[i] = i;
    values[i] = i * 10;
  }
  std::shuffle(keys.begin(), keys.end(), std::mt19937{std::random_device{}()});

  // 插入
  for (int i = 0; i < N; ++i) {
    map.set(&keys[i], &values[i]);
    assert(map.check());
  }

  // 查询/删除阶段
  for (int i = 0; i < N; ++i) {
    const int* val = map.get(&keys[i]);
    assert(val && *val == values[i]);
    map.remove(&keys[i]);
    assert(map.get(&keys[i]) == nullptr);
    assert(map.check());
  }

  std::cout << "All correctness checks passed!\n";
}

template <typename M>
void testRandomMapPerformance(const std::string& name, int N) {
  M map;
  std::vector<int> keys(N);
  std::vector<int> values(N);

  for (int i = 0; i < N; ++i) {
    keys[i] = i;
    values[i] = i * 10;
  }
  std::shuffle(keys.begin(), keys.end(), std::mt19937{std::random_device{}()});

  // 插入阶段
  auto start_insert = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < N; ++i) {
    map.set(&keys[i], &values[i]);
  }
  auto mid_insert = std::chrono::high_resolution_clock::now();

  // 查询阶段
  auto start_get = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < N; ++i) {
    const int* val = map.get(&keys[i]);
  }
  auto mid_get = std::chrono::high_resolution_clock::now();

  // 删除阶段
  auto start_remove = std::chrono::high_resolution_clock::now();
  for (int i = N-1; i >= 0; i--) {
    map.remove(&keys[i]);
  }
  auto end_remove = std::chrono::high_resolution_clock::now();

  std::cout << "Insert time: "
            << std::chrono::duration<double, std::milli>(mid_insert -
                                                         start_insert)
                   .count()
            << " ms\n";
  std::cout
      << "Get time:    "
      << std::chrono::duration<double, std::milli>(mid_get - start_get).count()
      << " ms\n";
  std::cout << "Remove time: "
            << std::chrono::duration<double, std::milli>(end_remove -
                                                         start_remove)
                   .count()
            << " ms\n";
}

template <typename M>
void testRandomMap(const std::string& name, int N) {
  std::cout << "\n=== Random Insert/Delete Test: " << name << " (N=" << N
            << ") ===\n";
  testRandomMapCorrectness<M>(name, N);
  testRandomMapPerformance<M>(name, N);
}

// --------------------------- 顺序插入 / 顺序删除 ---------------------------
template <typename M>
void testSequentialMapCorrectness(const std::string& name, int N) {
  M map;
  std::vector<int> keys(N);
  std::vector<int> values(N);

  for (int i = 0; i < N; ++i) {
    keys[i] = i;
    values[i] = i * 10;
  }

  // 插入
  for (int i = 0; i < N; ++i) {
    map.set(&keys[i], &values[i]);
    assert(map.check());
  }

  // 查询/删除阶段
  for (int i = 0; i < N; ++i) {
    const int* val = map.get(&keys[i]);
    assert(val && *val == values[i]);
    map.remove(&keys[i]);
    assert(map.get(&keys[i]) == nullptr);
    assert(map.check());
  }

  std::cout << "All correctness checks passed!\n";
}

template <typename M>
void testSequentialMapPerformance(const std::string& name, int N) {
  M map;
  std::vector<int> keys(N);
  std::vector<int> values(N);

  for (int i = 0; i < N; ++i) {
    keys[i] = i;
    values[i] = i * 10;
  }

  // 插入阶段
  auto start_insert = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < N; ++i) {
    map.set(&keys[i], &values[i]);
  }
  auto mid_insert = std::chrono::high_resolution_clock::now();

  // 查询阶段
  auto start_get = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < N; ++i) {
    const int* val = map.get(&keys[i]);
  }
  auto mid_get = std::chrono::high_resolution_clock::now();

  // 删除阶段
  auto start_remove = std::chrono::high_resolution_clock::now();
  for (int i = N-1; i >= 0; i--) {
    map.remove(&keys[i]);
  }
  auto end_remove = std::chrono::high_resolution_clock::now();

  std::cout << "Insert time: "
            << std::chrono::duration<double, std::milli>(mid_insert -
                                                         start_insert)
                   .count()
            << " ms\n";
  std::cout
      << "Get time:    "
      << std::chrono::duration<double, std::milli>(mid_get - start_get).count()
      << " ms\n";
  std::cout << "Remove time: "
            << std::chrono::duration<double, std::milli>(end_remove -
                                                         start_remove)
                   .count()
            << " ms\n";
}

template <typename M>
void testSequentialMap(const std::string& name, int N) {
  std::cout << "\n=== Sequantial Insert/Delete Test: " << name << " (N=" << N
            << ") ===\n";
  testSequentialMapCorrectness<M>(name, N);
  testSequentialMapPerformance<M>(name, N);
}

// --------------------------- 频繁交替增删测试 ---------------------------
template <typename M>
void testMixedOperationsCorrectness(const std::string& name, int N) {
  M map;
  std::vector<int> keys(N);
  std::vector<int> values(N);

  for (int i = 0; i < N; ++i) {
    keys[i] = i;
    values[i] = i * 10;
  }
  std::shuffle(keys.begin(), keys.end(), std::mt19937{std::random_device{}()});

  // 第一阶段：插入一半数据
  for (int i = 0; i < N / 2; ++i) {
    map.set(&keys[i], &values[i]);
    assert(map.check());
  }

  // 第二阶段：频繁交替操作
  // 操作模式：插入一批 -> 删除一批 -> 查询一批 -> 混合操作
  const int batch_size = N / 10;
  
  // 批次插入
  for (int i = N / 2; i < N / 2 + batch_size; ++i) {
    map.set(&keys[i], &values[i]);
    assert(map.check());
  }

  // 批次删除
  for (int i = 0; i < batch_size; ++i) {
    map.remove(&keys[i]);
    assert(map.check());
  }

  // 混合操作：插入、删除、查询交替进行
  for (int i = 0; i < batch_size; ++i) {
    // 插入新元素
    int insert_idx = N / 2 + batch_size + i;
    map.set(&keys[insert_idx], &values[insert_idx]);
    assert(map.check());

    // 查询现有元素
    int query_idx = N / 4 + i;
    const int* val = map.get(&keys[query_idx]);
    if (val) {
      assert(*val == values[query_idx]);
    }

    // 删除另一批元素
    int remove_idx = batch_size + i;
    map.remove(&keys[remove_idx]);
    assert(map.check());
  }

  // 最终验证和清理
  for (int i = 0; i < N; ++i) {
    const int* val = map.get(&keys[i]);
    if (val) {
      assert(*val == values[i]);
      map.remove(&keys[i]);
      assert(map.check());
    }
  }

  std::cout << "All mixed operations correctness checks passed!\n";
}

template <typename M>
void testMixedOperationsPerformance(const std::string& name, int N) {
  M map;
  std::vector<int> keys(N);
  std::vector<int> values(N);

  for (int i = 0; i < N; ++i) {
    keys[i] = i;
    values[i] = i * 10;
  }
  std::shuffle(keys.begin(), keys.end(), std::mt19937{std::random_device{}()});

  const int batch_size = N / 10;
  int operation_count = 0;

  auto start = std::chrono::high_resolution_clock::now();

  // 第一阶段：插入一半数据
  for (int i = 0; i < N / 2; ++i) {
    map.set(&keys[i], &values[i]);
    operation_count++;
  }

  // 第二阶段：频繁交替操作
  // 批次插入
  for (int i = N / 2; i < N / 2 + batch_size; ++i) {
    map.set(&keys[i], &values[i]);
    operation_count++;
  }

  // 批次删除
  for (int i = 0; i < batch_size; ++i) {
    map.remove(&keys[i]);
    operation_count++;
  }

  // 混合操作：插入、删除、查询交替进行
  for (int i = 0; i < batch_size; ++i) {
    // 插入新元素
    int insert_idx = N / 2 + batch_size + i;
    map.set(&keys[insert_idx], &values[insert_idx]);
    operation_count++;

    // 查询现有元素
    int query_idx = N / 4 + i;
    map.get(&keys[query_idx]);
    operation_count++;

    // 删除另一批元素
    int remove_idx = batch_size + i;
    map.remove(&keys[remove_idx]);
    operation_count++;
  }

  // 最终清理
  for (int i = 0; i < N; ++i) {
    if (map.get(&keys[i]) != nullptr) {
      map.remove(&keys[i]);
      operation_count++;
    }
  }

  auto end = std::chrono::high_resolution_clock::now();

  std::cout << "Total mixed operations: " << operation_count << "\n";
  std::cout << "Total time: "
            << std::chrono::duration<double, std::milli>(end - start).count()
            << " ms\n";
  std::cout << "Average time per operation: "
            << std::chrono::duration<double, std::micro>(end - start).count() / operation_count
            << " μs\n";
}

template <typename M>
void testMixedOperations(const std::string& name, int N) {
  std::cout << "\n=== Mixed Operations Test: " << name << " (N=" << N
            << ") ===\n";
  testMixedOperationsCorrectness<M>(name, N);
  testMixedOperationsPerformance<M>(name, N);
}

// --------------------------- 主函数 ---------------------------
int main() {
  const int N = 10000;

  // 随机插入 / 随机删除
  testRandomMap<Map<int, int, BST>>("BST Random", N);
  testRandomMap<Map<int, int, AVL>>("AVL Random", N);
  testRandomMap<Map<int, int, RBT>>("RBT Random", N);

  // 顺序插入 / 顺序删除
  testSequentialMap<Map<int, int, BST>>("BST Sequential", N);
  testSequentialMap<Map<int, int, AVL>>("AVL Sequential", N);
  testSequentialMap<Map<int, int, RBT>>("RBT Sequential", N);

  // 频繁交替增删测试
  testMixedOperations<Map<int, int, BST>>("BST Mixed", N);
  testMixedOperations<Map<int, int, AVL>>("AVL Mixed", N);
  testMixedOperations<Map<int, int, RBT>>("RBT Mixed", N);

  return 0;
}